home *** CD-ROM | disk | FTP | other *** search
/ Atari Mega Archive 1 / Atari Mega Archive - Volume 1.iso / gnu / flex / flexs237.zoo / nfa.c < prev    next >
C/C++ Source or Header  |  1990-06-28  |  18KB  |  718 lines
  1. /* nfa - NFA construction routines */
  2.  
  3. /*-
  4.  * Copyright (c) 1990 The Regents of the University of California.
  5.  * All rights reserved.
  6.  *
  7.  * This code is derived from software contributed to Berkeley by
  8.  * Vern Paxson.
  9.  * 
  10.  * The United States Government has rights in this work pursuant
  11.  * to contract no. DE-AC03-76SF00098 between the United States
  12.  * Department of Energy and the University of California.
  13.  *
  14.  * Redistribution and use in source and binary forms are permitted provided
  15.  * that: (1) source distributions retain this entire copyright notice and
  16.  * comment, and (2) distributions including binaries display the following
  17.  * acknowledgement:  ``This product includes software developed by the
  18.  * University of California, Berkeley and its contributors'' in the
  19.  * documentation or other materials provided with the distribution and in
  20.  * all advertising materials mentioning features or use of this software.
  21.  * Neither the name of the University nor the names of its contributors may
  22.  * be used to endorse or promote products derived from this software without
  23.  * specific prior written permission.
  24.  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED
  25.  * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
  26.  * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  27.  */
  28.  
  29. #ifndef lint
  30. static char rcsid[] =
  31.     "@(#) $Header: /usr/fsys/odin/a/vern/flex/RCS/nfa.c,v 2.6 90/06/27 23:48:29 vern Exp $ (LBL)";
  32. #endif
  33.  
  34. #include "flexdef.h"
  35.  
  36.  
  37. /* declare functions that have forward references */
  38.  
  39. int dupmachine PROTO((int));
  40. void mkxtion PROTO((int, int));
  41.  
  42.  
  43. /* add_accept - add an accepting state to a machine
  44.  *
  45.  * synopsis
  46.  *
  47.  *   add_accept( mach, accepting_number );
  48.  *
  49.  * accepting_number becomes mach's accepting number.
  50.  */
  51.  
  52. void add_accept( mach, accepting_number )
  53. int mach, accepting_number;
  54.  
  55.     {
  56.     /* hang the accepting number off an epsilon state.  if it is associated
  57.      * with a state that has a non-epsilon out-transition, then the state
  58.      * will accept BEFORE it makes that transition, i.e., one character
  59.      * too soon
  60.      */
  61.  
  62.     if ( transchar[finalst[mach]] == SYM_EPSILON )
  63.     accptnum[finalst[mach]] = accepting_number;
  64.  
  65.     else
  66.     {
  67.     int astate = mkstate( SYM_EPSILON );
  68.     accptnum[astate] = accepting_number;
  69.     mach = link_machines( mach, astate );
  70.     }
  71.     }
  72.  
  73.  
  74. /* copysingl - make a given number of copies of a singleton machine
  75.  *
  76.  * synopsis
  77.  *
  78.  *   newsng = copysingl( singl, num );
  79.  *
  80.  *     newsng - a new singleton composed of num copies of singl
  81.  *     singl  - a singleton machine
  82.  *     num    - the number of copies of singl to be present in newsng
  83.  */
  84.  
  85. int copysingl( singl, num )
  86. int singl, num;
  87.  
  88.     {
  89.     int copy, i;
  90.  
  91.     copy = mkstate( SYM_EPSILON );
  92.  
  93.     for ( i = 1; i <= num; ++i )
  94.     copy = link_machines( copy, dupmachine( singl ) );
  95.  
  96.     return ( copy );
  97.     }
  98.  
  99.  
  100. /* dumpnfa - debugging routine to write out an nfa
  101.  *
  102.  * synopsis
  103.  *    int state1;
  104.  *    dumpnfa( state1 );
  105.  */
  106.  
  107. void dumpnfa( state1 )
  108. int state1;
  109.  
  110.     {
  111.     int sym, tsp1, tsp2, anum, ns;
  112.  
  113.     fprintf( stderr, "\n\n********** beginning dump of nfa with start state %d\n",
  114.          state1 );
  115.  
  116.     /* we probably should loop starting at firstst[state1] and going to
  117.      * lastst[state1], but they're not maintained properly when we "or"
  118.      * all of the rules together.  So we use our knowledge that the machine
  119.      * starts at state 1 and ends at lastnfa.
  120.      */
  121.  
  122.     /* for ( ns = firstst[state1]; ns <= lastst[state1]; ++ns ) */
  123.     for ( ns = 1; ns <= lastnfa; ++ns )
  124.     {
  125.     fprintf( stderr, "state # %4d\t", ns );
  126.  
  127.     sym = transchar[ns];
  128.     tsp1 = trans1[ns];
  129.     tsp2 = trans2[ns];
  130.     anum = accptnum[ns];
  131.  
  132.     fprintf( stderr, "%3d:  %4d, %4d", sym, tsp1, tsp2 );
  133.  
  134.     if ( anum != NIL )
  135.         fprintf( stderr, "  [%d]", anum );
  136.  
  137.     fprintf( stderr, "\n" );
  138.     }
  139.  
  140.     fprintf( stderr, "********** end of dump\n" );
  141.     }
  142.  
  143.  
  144. /* dupmachine - make a duplicate of a given machine
  145.  *
  146.  * synopsis
  147.  *
  148.  *   copy = dupmachine( mach );
  149.  *
  150.  *     copy - holds duplicate of mach
  151.  *     mach - machine to be duplicated
  152.  *
  153.  * note that the copy of mach is NOT an exact duplicate; rather, all the
  154.  * transition states values are adjusted so that the copy is self-contained,
  155.  * as the original should have been.
  156.  *
  157.  * also note that the original MUST be contiguous, with its low and high
  158.  * states accessible by the arrays firstst and lastst
  159.  */
  160.  
  161. int dupmachine( mach )
  162. int mach;
  163.  
  164.     {
  165.     int i, init, state_offset;
  166.     int state = 0;
  167.     int last = lastst[mach];
  168.  
  169.     for ( i = firstst[mach]; i <= last; ++i )
  170.     {
  171.     state = mkstate( transchar[i] );
  172.  
  173.     if ( trans1[i] != NO_TRANSITION )
  174.         {
  175.         mkxtion( finalst[state], trans1[i] + state - i );
  176.  
  177.         if ( transchar[i] == SYM_EPSILON && trans2[i] != NO_TRANSITION )
  178.         mkxtion( finalst[state], trans2[i] + state - i );
  179.         }
  180.  
  181.     accptnum[state] = accptnum[i];
  182.     }
  183.  
  184.     if ( state == 0 )
  185.     flexfatal( "empty machine in dupmachine()" );
  186.  
  187.     state_offset = state - i + 1;
  188.  
  189.     init = mach + state_offset;
  190.     firstst[init] = firstst[mach] + state_offset;
  191.     finalst[init] = finalst[mach] + state_offset;
  192.     lastst[init] = lastst[mach] + state_offset;
  193.  
  194.     return ( init );
  195.     }
  196.  
  197.  
  198. /* finish_rule - finish up the processing for a rule
  199.  *
  200.  * synopsis
  201.  *
  202.  *   finish_rule( mach, variable_trail_rule, headcnt, trailcnt );
  203.  *
  204.  * An accepting number is added to the given machine.  If variable_trail_rule
  205.  * is true then the rule has trailing context and both the head and trail
  206.  * are variable size.  Otherwise if headcnt or trailcnt is non-zero then
  207.  * the machine recognizes a pattern with trailing context and headcnt is
  208.  * the number of characters in the matched part of the pattern, or zero
  209.  * if the matched part has variable length.  trailcnt is the number of
  210.  * trailing context characters in the pattern, or zero if the trailing
  211.  * context has variable length.
  212.  */
  213.  
  214. void finish_rule( mach, variable_trail_rule, headcnt, trailcnt )
  215. int mach, variable_trail_rule, headcnt, trailcnt;
  216.  
  217.     {
  218.     add_accept( mach, num_rules );
  219.  
  220.     /* we did this in new_rule(), but it often gets the wrong
  221.      * number because we do it before we start parsing the current rule
  222.      */
  223.     rule_linenum[num_rules] = linenum;
  224.  
  225.     /* if this is a continued action, then the line-number has
  226.      * already been updated, giving us the wrong number
  227.      */
  228.     if ( continued_action )
  229.     --rule_linenum[num_rules];
  230.  
  231.     fprintf( temp_action_file, "case %d:\n", num_rules );
  232.  
  233.     if ( variable_trail_rule )
  234.     {
  235.     rule_type[num_rules] = RULE_VARIABLE;
  236.  
  237.     if ( performance_report )
  238.         fprintf( stderr, "Variable trailing context rule at line %d\n",
  239.              rule_linenum[num_rules] );
  240.  
  241.     variable_trailing_context_rules = true;
  242.     }
  243.  
  244.     else
  245.     {
  246.     rule_type[num_rules] = RULE_NORMAL;
  247.  
  248.     if ( headcnt > 0 || trailcnt > 0 )
  249.         {
  250.         /* do trailing context magic to not match the trailing characters */
  251.         char *scanner_cp = "yy_c_buf_p = yy_cp";
  252.         char *scanner_bp = "yy_bp";
  253.  
  254.         fprintf( temp_action_file,
  255.     "*yy_cp = yy_hold_char; /* undo effects of setting up yytext */\n" );
  256.  
  257.         if ( headcnt > 0 )
  258.         fprintf( temp_action_file, "%s = %s + %d;\n",
  259.              scanner_cp, scanner_bp, headcnt );
  260.  
  261.         else
  262.         fprintf( temp_action_file,
  263.              "%s -= %d;\n", scanner_cp, trailcnt );
  264.     
  265.         fprintf( temp_action_file,
  266.              "YY_DO_BEFORE_ACTION; /* set up yytext again */\n" );
  267.         }
  268.     }
  269.  
  270.     line_directive_out( temp_action_file );
  271.     }
  272.  
  273.  
  274. /* link_machines - connect two machines together
  275.  *
  276.  * synopsis
  277.  *
  278.  *   new = link_machines( first, last );
  279.  *
  280.  *     new    - a machine constructed by connecting first to last
  281.  *     first  - the machine whose successor is to be last
  282.  *     last   - the machine whose predecessor is to be first
  283.  *
  284.  * note: this routine concatenates the machine first with the machine
  285.  *  last to produce a machine new which will pattern-match first first
  286.  *  and then last, and will fail if either of the sub-patterns fails.
  287.  *  FIRST is set to new by the operation.  last is unmolested.
  288.  */
  289.  
  290. int link_machines( first, last )
  291. int first, last;
  292.  
  293.     {
  294.     if ( first == NIL )
  295.     return ( last );
  296.  
  297.     else if ( last == NIL )
  298.     return ( first );
  299.  
  300.     else
  301.     {
  302.     mkxtion( finalst[first], last );
  303.     finalst[first] = finalst[last];
  304.     l